package com.nowcoder.code.lcof;

import java.util.PriorityQueue;

public class JZ41 {

    public static void main(String[] args) {

        JZ41 jz41 = new JZ41();
        int[] i = new int[]{5, 2, 3, 4, 1, 6, 7, 0, 8};

        for (int j : i) {
            jz41.Insert(j);
            System.out.println(jz41.GetMedian());

        }
    }

    PriorityQueue<Integer> k0 = new PriorityQueue<>(((o1, o2) -> o2 - o1));
    PriorityQueue<Integer> k1 = new PriorityQueue<>();


    public void Insert(Integer num) {
        k0.add(num);
        k1.add(k0.poll());
        if (k1.size() > k0.size()) {
            k0.add(k1.poll());
        }
    }

    public Double GetMedian() {
        if (k0.size() > k1.size()) {
            return k0.peek().doubleValue();
        } else {
            return (k0.peek().doubleValue() + k1.peek().doubleValue()) / 2;
        }
    }

}
